package allwe.leetcode.LCR_078;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 美团算法
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6,7,8,9]] 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ]
 * 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
 */
public class NO78_1 {

    public static void main(String[] args) {

        LinkedList<Integer> list1 = new LinkedList<>(Arrays.asList(1,4,5));

        LinkedList<Integer> list2 = new LinkedList<>(Arrays.asList(1,3,4));

        LinkedList<Integer> list3 = new LinkedList<>(Arrays.asList(2,6));

        ArrayList<LinkedList<Integer>> baseList = new ArrayList<>();
        baseList.add(list1);
        baseList.add(list2);
        baseList.add(list3);

        System.out.println(sort(baseList));
    }

    public static ArrayList<Integer> sort(ArrayList<LinkedList<Integer>> baseList) {
        // 计算结果集大小 - 避免扩容操作
        int listSize = baseList.stream().mapToInt(LinkedList::size).sum();
        // 准备容器存放结果
        ArrayList<Integer> result = new ArrayList<>(listSize);
        // 准备容器记录每一个子列表的指针
        int[] pointerArray = new int[baseList.size()];
        // 死循环
        while (true) {
            int count = listSize;       // 设定跳出死循环条件
            Integer minItem = null;     // 记录当前轮次的最小值
            Integer childListId = null; // 记录这个最小值的来源子列表
            // 反复循环主列表
            for (int i = 0; i < baseList.size(); i++) {
                LinkedList<Integer> childList = baseList.get(i);
                // 跳过已经用光的子列表
                if (childList.size() <= pointerArray[i]) {
                    --count;
                    continue;
                }
                // 每个子列表取出自己指针对应的值
                Integer childItem = childList.get(pointerArray[i]);
                // 设定当前轮次的初始值
                if (minItem == null) {
                    minItem = childItem;
                    childListId = i;
                    continue;
                }
                // 做比较，取最小值,更新最小值的来源子列表
                if (childItem < minItem) {
                    minItem = childItem;
                    childListId = i;
                }
            }
            // 跳出死循环
            if (count == 0 || minItem == null) {
                break;
            }
            // 收集当前轮次的最小值
            result.add(minItem);
            // 更新指针
            pointerArray[childListId]++;
        }
        // 输出结果
        return result;
    }
}
